A distributed computer system includes several processors that cooperate to perform a task. To cooperate more effectively, the processors often send messages to each other. One method of sending a message from one processor to another is to maintain a message-list in a memory that is accessible to all the processors. Each processor can periodically scan this message-list for messages. A processor can thus post a message in that message-list. Eventually, the processor for which that message is intended will scan the message-list and encounter that message.
The message-list is typically an ordered sequence of messages having a first message and a last message. These messages are arranged in the order in which a scanning processor will encounter them. In most cases, the messages are arranged in chronological order, with the oldest message being at the beginning of the message-list and the most recently posted messages near the end of the message-list.
A scanning processor typically scans a message-list by beginning at the first message and proceeding sequentially through the message-list until it either reaches the last message or until it encounters a message for which it is an intended recipient. This ensures that the scanning processor will encounter older messages before it encounters newer messages. If the scanning processor encounters a message for which it is an intended recipient, it interrupts its scan to retrieve and process that message. The next time the scanning processor scans the message-list, it begins again at the first message of the message-list. This simple scanning method guarantees that the scanning processor will always encounter older messages before it encounters newer messages.
One property of this scanning method is that a scanning processor may inspect messages far more often than necessary. In particular, messages near the beginning of the message-list are likely to be repeatedly inspected. Where the distributed computing system has only a small number of processors, the message-list is not very long. Hence, the repeated inspection of messages near the beginning of the message list does not consume appreciable amounts of time.
As distributed computing systems have become more complex, the number of processors within such systems has grown. As a result, the message-lists in such systems have lengthened. Because of this, the time spent unnecessarily re-inspecting messages has become more significant.